package com.shangguigu.search;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2019/10/14
 * @description: 二分查找
 * 首先保证有序
 */
public class BinarySearch {

	/**
	 * 查找排序数组中元素的索引位置
	 * 迭代的方法
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int binaryArrSearch(int[] nums, int target) {
		Arrays.sort(nums);
		int left = 0, right = nums.length, mid = 0;
		while (left < right) {
			mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				return mid;
			}
			///当二分不再变动时，跳出死循环
			if (mid == left) {
				break;
			}
			///如果小于目标值
			else if (nums[mid] < target) {
				left = mid;
			} else {
				right = mid;
			}
		}
		return -1;
	}

	/**
	 * 递归方法
	 *
	 * @param nums
	 * @param left
	 * @param right
	 * @param findVal
	 * @return
	 */
	public static int binaryArrSearch(int[] nums, int left, int right, int findVal) {
		if (left > right) {
			return -1;
		}
		int mid = left + (right - left) / 2;
		int val = nums[mid];
		///二分值小于目标值时，left=mid+1(由于mid已经比较过了)
		if (findVal > val) {
			return binaryArrSearch(nums, mid+1, right, findVal);
		}else if (findVal < val){
			return binaryArrSearch(nums, left, mid-1, findVal);
		}else {
			return mid;
		}
	}

	public static void main(String[] args) {
		int[] nums = new int[]{1, 8, 10, 89, 1000, 1890};
		int index = binaryArrSearch(nums, 1);
		int index2 = binaryArrSearch(nums, 0, nums.length-1, 1);
		System.out.println(index);
		System.out.println(index2);
	}
}
